The invention relates to communications between a master station and one or more slave stations. More specifically, the invention relates to a master station selecting subset(s) of the slave stations by broadcasting commands with conditions that the selected slaves meet.
In the prior art, a master control unit is to communicate with a plurality of autonomous and independent slaves. In such environment, the number of slaves is often not known a priori. There may in fact be no slaves with which the master can communicate. Among the reasons the master may have to communicate with the slaves are (a) the need to acknowledge their presence, (b) identify and count them and/or (c) order them to perform tasks. This kind of computational environment falls under the broad category of broadcasting sequential processes, which is defined by Narain Gehani in Chapter 9 of the book co-edited with Andrew McGettrick, xe2x80x9cConcurrent Programmingxe2x80x9d (Addison-Wesley, 1988), which is herein incorporated by reference in its entirety.
Because the master often does not know ahead of time the number of slaves present and because that number may be very large and possibly unyieldy, it is advantageous for the master to be able to select a subset of the slaves with whom to communicate further. Such a selection must of course be done by a conditional. Those slaves that meet the condition are thus considered selected, while those that do not meet the condition are considered not selected. The selection is performed by broadcasting to all slaves the condition that must be met. This is akin to asking those among a large crowd of people whose last name is Lowell to raise their hand. Each slave is defined has having at least the capability to listen to the master""s broadcasts, to receive the broadcast condition and to self-test so as to determine whether it meets the condition. See for example, U.S. patent application Ser. No. 08/303,965, entitled xe2x80x9cRadio Frequency (RF) Group Select Protocolxe2x80x9d to Cesar et al. filed on Sep. 9, 1994 which is herein incorporated by reference in its entirety.
Practical environments where this computational model can be applied include bus arbitration, wireless communication, distributed and parallel processing. Characteristic of such environments is the existence of a protocol for how master and slaves communicate. The aforementioned capability of subset selection can be an important additional component of that protocol.
Finite state-machines are a well-known modelling tool. The set theory that often accompanies the definition of finite state-machines is also well known. Both subjects are amply covered in any of many books on discrete or finite mathematics that are available today. The book by Ralph Grimaldi, xe2x80x9cDiscrete and Combinatorial Mathematics: An Applied Introductionxe2x80x9d (Addison-Wesley, 1985), is a fine example of its kind.
In the prior art, the methods used for selecting subsets of slaves is limited to comparisons against the information held by the slaves such that the comparison is either true or false and the slaves can be in either of two selection states: selected or not selected. The slave may contain many other states, but only two are effectively dedicated to the purpose of subset selection.
In some older prior art, a comparison will override a previous comparison. There is no notion of accumulating and combining successive comparisons to effect a selection according to a complex condition.
More recent prior art allows slaves to move between two selection states according to successive comparisons. That allows some complex conditions to be effected. However not all complex conditions can be effected with such two-selection-state machine. For example, the complex condition xe2x80x9cis-red and is-not tall or is-not-red and is-tallxe2x80x9d, that is, the EXCLUSIVE-OR of the two simple comparisons xe2x80x9cis-redxe2x80x9d and xe2x80x9cis-tallxe2x80x9d, can not be performed such that the subset of slaves that satisfy the EXCLUSIVE-OR are in the first state and those that do not satisfy the EXCLUSIVE-OR are in the second state. In the case of complex conditions involving two comparisons and their negation, the two-selection-state machine can not perform the EXCLUSIVE-OR and the EQUIVALENCE logical operators. In the case of complex conditions involving more than two comparisons and their negation, the two-selection-state machine can not perform an increasingly large number of logical equations.
In the prior art, conditions such as the EXCLUSIVE-OR must be broken up into two independent processing steps. First, slaves satisfying the first AND term are selected and all necessary processing sequence is performed over them. Second, after a general reset, slaves satisfying the second AND term are selected and the same necessary processing sequence is repeated over those. That means that the processing sequence must be broadcast twice. In the case of more complicated conditions, rebroadcasting of such sequence may happen more than twice. For example, the condition (A*xcx9cB*xcx9cC)+(xcx9cA*B*xcx9cC)+(xcx9cA*xcx9cB+C) would need three rebroadcasts.
The only conditions that can be executed in a single round of broadcasting by a two-selection-state logic as used by the prior art are those conditions that can be expressed by a left-nested expressions, such as ((A+B+C)*D*E)+F). OR conditions, such as (A+B+C+D), and AND conditions, such as (A*B*C), are particular cases of left-nested expressions. In contrast, EXCLUSIVE-OR type conditions, such as (A*B*xcx9cC)+(A*xcx9cB*C)*(xcx9cA*B*C), can not be written as left-nested expressions and therefore can not be handled by the two-selection-state logic.
Among the prior art is U.S. Pat. No. 5,434,572, entitled xe2x80x9cSystem and Method for Initiating Communications between a Controller and a Selected Subset of Multiple Transponders in a Common RF Fieldxe2x80x9d to Smith dated Jul. 18, 1995. The method begins by selecting all xe2x80x9ctranspondersxe2x80x9d in a field and, by a sequence of commands, incrementally moving groups of slaves to a xe2x80x9cresetxe2x80x9d condition.
In the U.S. Pat. No. 5,410,315, entitled xe2x80x9cGroup-Addressable Transponder Arrangementxe2x80x9d to Huber dated Apr. 25, 1995, a selection is essentially made through a comparison against a xe2x80x9cgroup and/or unit addressxe2x80x9d. Unlike Smith, there is no progressive incremental refinement. Huber can perform only limited AND operations.
An object of this invention is a system and method for using arbitrarily complex logical conditions to select slave stations that satisfy those conditions transmitted by a master station through a series one or more commands.
An object of this invention is a system and method for using arbitrarily complex logical conditions to select RF transponders that satisfy those conditions transmitted by a base station through a series one or more commands.
The present invention is a system and method for selecting a subset of a plurality of autonomous and independent slaves, wherein each slave comprises (i) a three-state machine dedicated to selection, (ii) some other stored information, and (iii) a logic to execute externally provided commands in a command sequence that exercise the three-state machine. The primary purpose of the commands is to effect state transitions. The slave receives the command, which causes a comparison to be performed against the slave""s stored information, the results of which possibly causing a state transition in the slave.
The commands, in a sequence called a command sequence, are broadcast from at least one master control unit to zero or more slaves. The exact number of slaves may not be known by the master. The master executes a method by which a sequence of discrete commands is broadcast to all slaves. The overall purpose of the method is to bring a subset of the slaves to be at the same state of their three-state machine, while all other slaves are at any one of the two other remaining states.
A three-state machine dedicated to selection is present in every slave. Each slave is at one of those three states, therefore, at any one time, the slaves can be subdivided into three subsets: those slaves that have their selection three-state machine at the first state, those at the second state, and those at the third state. In a preferred embodiment, transitions are possible between any two states of the three-state machine. Transitions are requested by command (sequence) broadcast from the master. A command specifies a desired transition, say from the second state to the first state. Only slaves that are at the second state may be affected. The command also specifies a condition under which the transition will occur. If the condition is met, the transition is effected; if not, the slave remains in its previous state.
In a preferred embodiment, slaves can be moved from a first state to a second state and visa versa. Only slaves in the second state can be moved to a third state. The slaves in the third state ignore the remaining commands in the command sequence. In alternative preferred embodiments, the first and second states reverse roles after an end of one or more subsequences in the sequences of commands. Also, the second and third states can reverse roles after an end of one or more subsequences. Further, the states of the slaves can cycle their roles at the end of one or more of the subsequences.